/**
 * Copyright (c) 2020-2021 浦东大爷 All rights reserved.
 * 机会永远都是留给有准备的人
 */
package com.job.moudle3.task2;

/**
 * @author: gitwo
 * @date: 2020-11-22
 * @description:编程获取两个指定字符串中的最大相同子串。
 */
public class MaxPubStringTest {

    /**
     * 通过动态规划的方式获取最大公共子串
     */
    public static String getPubStr(String str1, String str2) {
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int[][] m = new int[c2.length+1][c1.length+1];
        for (int i = 1; i <= c2.length; i++) {
            for (int j = 1; j <= c1.length; j++) {
                if (c2[i - 1] == c1[j - 1])
                    m[i][j] = m[i - 1][j - 1] + 1; // 通过状态转移寻找最优子串
            }
        }
        int max = 0;
        int index = 0;
        for (int i = 0; i <= c2.length; i++) {
            for (int j = 0; j <= c1.length; j++) {
//                System.out.print(m[i][j] + "\t");
                if (m[i][j] > max) {
                    max = m[i][j];// 寻找最大子串
                    index = i;
                }
            }
//            System.out.println("");
        }
        String s = "";
        for (int i = index - max; i < index; i++)
            s += str2.charAt(i); // 取出最大子串并返回
        return s;
    }

    public static void main(String[] args) {
        String a = "asdafabcdghjkaabcde";
        String b = "aaasabcdedfg";
        String maxPubString = getPubStr(a, b);
        System.out.println("字符串1：" + a);
        System.out.println("字符串2：" + b);
        System.out.println("最大公共子串：" + maxPubString);
    }
}
